package com.ztom.dp;

/**
 * 跳跃游戏 2
 * <p>
 * https://leetcode-cn.com/problems/jump-game-ii/
 *
 * @author ZhangTao
 */
public class Code09Jump {

    public int jump1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int t = nums.length - 1;
        int steps = 0;
        // 反向跳跃
        while (t > 0) {
            // 每次从最左开始跳, 力求最远, 步数越少
            for (int i = 0; i < t; i++) {
                if (i + nums[i] >= t) {
                    t = i;
                    steps++;
                    // 继续下次跳跃
                    break;
                }
            }
        }
        return steps;
    }

    public int jump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        // 记录当前能跳到的最右位置的下标
        int rightMost = 0;
        // 记录每一步可跳跃范围的右边界
        int right = 0;
        // 记录步数
        int steps = 0;
        // 最后一格不需要跳
        for (int i = 0; i < n - 1; i++) {
            rightMost = Math.max(rightMost, i + nums[i]);
            // 如果当前这一步 刚好到达最大可跳跃位置, 更新下一步最大可跳跃位置
            if (i == right) {
                right = rightMost;
                steps++;
            }
        }
        return steps;
    }
}
